Học máy (Machine Learning)
Support Vector Machines (SVM)
Vinh, 08/2021
By Hoàng Hữu Việt
Email: viethh@vinhuni.edu.vn
Viện Kỹ thuật và Công nghệ, Đại học Vinh
Tài liệu tham khảo
Tài liệu chính
[1] Richard O.Duda, Peter E. Hart, David G.Stock. Pattern Classification, 2nd, Wiley,
2001.
[2] Hữu Tiệp, Machine Learning bản, 2020
Nội dung
Máy véc- hỗ trợ tuyến tính
Máy véc- hỗ trợ lề mềm
Máy véc- hỗ trợ hạt nhân
dụ nhận dạng chữ số viết tay với SVM
dụ nhận dạng ảnh mặt người với SVM
Bài tập
Giới thiệu
Thuật toán máy véc- hỗ trợ được giới thiệu năm 1992
[1] B.E. Boser et al. A Training Algorithm for Optimal Margin Classifiers.
Proceedings of the Fifth Annual Workshop on Computational Learning Theory,
144-152, Pittsburgh, 1992.
Thuật toán máy c- hỗ trợ một thuật toán được sử dụng trong
nhiều ứng dụng của học máy.
Bài toán nhận dạng chữ số viết tay
Bài toán nhận dạng ảnh mặt người
Bài toán nhận dạng vân tay
Máy véc-tơ hỗ trợ tuyến tính
Phân lớp dữ liệu tách biệt tuyến tính:
Tìm một đường thẳng/siêu phẳng sao cho tất cả các điểm thuộc lớp 1 (class 1)
thuộc về cùng một phía các điểm lớp 2 (class 2) thuộc về cùng một phía.
số đường thẳng/siêu phẳng, vậy đường thẳng/siêu phẳng nào tốt nhất?
Làm thế nào để tìm được đường thẳng/siêu phẳng tốt nhất?
Class 1
Class 2
Class 1
Class 2
Class 1
Class 2
Máy véc-tơ hỗ trợ tuyến tính
Lề (margin) của một lớp được định nghĩa khoảng cách từ các điểm
gần nhất của lớp đó tới đường thẳng/siêu phẳng phân lớp.
Tìm lề của 2 lớp bằng nhau lớn nhất máy véc- hỗ trợ tuyến tính.
Class 1
Class 2
Class 1
Class 2
Khoảng cách từ điểm 󰇛
󰇜
đến một siêu phẳng
, 󰉵
󰇛
󰇜


Trong không gian 2 chiều:



Tham khảo cách tính phụ lục.
Máy véc-tơ hỗ trợ tuyến tính
Class 1
Class 2
󰇛󰇜
Máy véc-tơ hỗ trợ tuyến tính
Giả sử mặt phân chia phương trình

Bằng cách nhân các hệ số với các
hằng số phù hợp, ta thể giả sử rằng:
Điểm gần nhất của lớp 1 tới mặt phân chia
thõa mãn:
1.
Điểm gần nhất của lớp 2 tới mặt phân chia
thõa mãn:
-1.
Class 1
Class 2
󰇛󰇜
Máy véc-tơ hỗ trợ tuyến tính
Giả sử tập huấn luyện gồm mẫu dữ liệu:
󰇝
󰇞 với
󰇛 󰇜 được gán nhãn lớp +1
-1.
Với cặp dữ liệu
, khoảng cách từ
tới mặt phẳng phân chia :
󰇛
󰇜
Tìm để lề đạt giá trị lớn nhất:



󰇛
󰇜



󰇛
󰇜
Class 1
Class 2
󰇛󰇜
Máy véc-tơ hỗ trợ tuyến tính
cho những điểm biên, do vậy với mọi
ta :
.
Bài toán SVM được đưa về bài toán tối ưu ràng buộc, tức tìm :


với
Hoặc:

với
Đây bài toán tối ưu bậc 2 (quadratic optimization problem) được
giải bằng phương pháp Lagrangian Multiplers.
Với mẫu dữ liệu mới,

, nhãn dữ liệu



Máy véc-tơ hỗ trợ tuyến tính
Lập trình bằng Python ?
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
X_train = np.array([[1,0], [0,1], [1,1], [0,2], [4,1], [2,2], [3,2],[1,4],[0,4]])
y_train = np.array([-1, -1, -1, -1, 1, 1, 1, 1, 1])
# SVM
model = SVC(kernel='linear', C = 1.0)
model.fit(X_train, y_train)
w = model.coef_
b = model.intercept_
print('w = ', w,'b = ',b)
z = np.array([[0,0]])
print(model.predict(z))
plt.grid(True)
plt.plot(X_train[:4, 0], X_train[:4, 1], 'ro', markersize = 8)
plt.plot(X_train[4:, 0], X_train[4:, 1], 'bs', markersize = 8)
x1 = np.linspace(-1,4)
x2 = -(w[0,0]*x1 + b)/w[0,1]
plt.plot(x1,x2, 'b')
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Class 2
Class 1
Máy véc- hỗ trợ lề mềm
Nếu tập mẫu không tách biệt tuyến
tính?
Cho phép “lỗi”
x
i
trong phân lớp.
Tức
x
i
xấp xỉ với số mẫu phân lớp
sai.
Ta cần tối thiểu
i
x
i
, với x
i
được
tính:
x
i
gọi biến lùi,
x
i
= 0 không lỗi.
Class 1
Class 2
w
Máy véc- hỗ trợ lề mềm
Tìm
x
i
để thõa mãn:
x
i
 
x

x
i
với
x
i
,
x
i
0 C
một hằng số điều khiển lỗi.
Nếu
x
i
= 0, các điểm
x
i
nằm trong
vùng an toàn.
Nếu
x
i
, các điểm
x
i
không
nằm trong vùng an toàn những vẫn
phân loại đúng.
Nếu
x
i
>1, các điểm
x
i
phân loại sai.
Class 1
Class 2
w
Máy véc-tơ hỗ trợ hạt nhân
Máy véc- hỗ trợ hạt nhân (support vector machines with kernel
functions)
Tính toán trong không gian đặc trưng độ phức tạp lớn hơn nhiều so
với không gian ban đầu.
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f(.)
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
Feature space
Input space
Note: feature space is of higher dimension than the input space in practice
Máy véc-tơ hỗ trợ hạt nhân
Ý tưởng: các mẫu dữ liệu trong không gian ban đầu được chuyển tới
không gian đặc trưng trong đó các mẫu dữ liệu tách tuyến tính.
Chuyển bài toán về SVM tuyến tính/lề mềm để giải.
Φ: x φ(x)
Máy véc-tơ hỗ trợ hạt nhân
Một số hàm hạt nhân thường được sử dụng:
Máy véc-tơ hỗ trợ hạt nhân
dụ bài toán XOR
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
# XOR dataset and targets
X_train = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
y_train = np.array([0, 0, 1, 1])
fignum = 1
# fit the model
for kernel in ('sigmoid', 'poly', 'rbf'):
model = SVC(kernel = kernel, gamma = 4, coef0 = 0)
model.fit(X_train, y_train)
# plot the line, the points, and the nearest vectors to the plane
fig, ax = plt.subplots()
plt.figure(fignum, figsize=(1, 1))
plt.clf()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Máy véc-tơ hỗ trợ hạt nhân
plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=80, facecolors='None')
plt.plot(X_train[:2, 0], X_train[:2, 1], 'ro', markersize = 8)
plt.plot(X_train[2:, 0], X_train[2:, 1], 'bs', markersize = 8)
plt.axis('tight')
x_min = y_min = -2
x_max = y_max = 3
X, Y = np.mgrid[x_min:x_max:200j, y_min:y_max:200j]
Z = model.decision_function(np.c_[X.ravel(), Y.ravel()])
# Put the result into a color plot
Z = Z.reshape(X.shape)
plt.figure(fignum, figsize=(4, 3))
CS = plt.contourf(X, Y, np.sign(Z), 200, cmap='jet', alpha=.2)
plt.contour(X, Y, Z, colors=['k', 'k', 'k'], linestyles=['--', '-', '--'], levels=[-.5, 0, .5])
plt.title(kernel, fontsize=15)
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
fignum = fignum + 1
plt.show()
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Một số mẫu chữ số viết tay
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Đọc chuẩn hóa dữ liệu
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import warnings
warnings.filterwarnings('ignore')
# import API functions
from keras.datasets import mnist
(X_train,y_train),(X_test,y_test) = mnist.load_data()
# get the image parameters
num_train_samples = X_train.shape[0] # 60000
num_test_samples = X_test.shape[0] # 10000
height = X_train.shape[1] # 28
width = X_train.shape[2] # 28
# normalize the data samples
X_train = X_train.reshape(num_train_samples, height*width) # 28x28 -> 784x1
X_train = X_train.astype('float32') / 255 # convert values to [0,1]
X_test = X_test.reshape(num_test_samples, height*width) # 28x28 -> 784x1
X_test = X_test.astype('float32') / 255 # convert values to [0,1]
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Tìm tham số C
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score
# determine c
X_train_accuracy = []
X_test_accuracy = []
for c in [0.001,0.01,0.1,1,10]:
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
X_train_accuracy.append(accuracy_score(y_train, y_train_pred))
X_test_accuracy.append(accuracy_score(y_test, y_test_pred))
# plot for determining c
c = [0.001,0.01,0.1,1,10]
import matplotlib.pyplot as plt
plt.subplots(figsize=(10, 5))
plt.semilogx(c, X_train_accuracy,'-gD', color = 'blue', label="Training Accuracy")
plt.semilogx(c, X_test_accuracy,'-gD', color='red' , label="Testing Accuracy")
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Vẽ tỷ lệ nhận dạng theo tham số C, nhận dạng với C tìm được
plt.grid(True)
plt.xlabel("Cost Parameter C",fontsize=14)
plt.ylabel("Accuracy",fontsize=14)
plt.legend()
plt.title('Accuracy versus the Cost Parameter C (log-scale)')
plt.show()
# run for c = 0.1
c = 0.1
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
# predict
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
# accuracy
X_train_accuracy = accuracy_score(y_train, y_train_pred)
X_test_accuracy = accuracy_score(y_test, y_test_pred)
#
print(X_train_accuracy)
print(X_test_accuracy)
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Tỷ lệ nhận dạng tập huấn luyện: 95.87%
Tỷ lệ nhận dạng tập kiểm tra: 94.72%
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Cho 2 thư mục ifd-train ifd-test chứa các ảnh mặt người của 61
người, trong đó:
T mục ifd-train chứa ảnh dùng để huấn luyện t mục ifd-test dùng chứa
các ảnh nhận dạng.
Tên tệp trong 2 thư mục chứa một dấu - các tự trước dấu - biểu diễn lớp
dữ liệu của ảnh, các tự sau dấu - số thứ tự hnh nh mặt của mỗi người.
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Đọc dữ liệu huấn luyện Đọc dữ liệu kiểm tra
import numpy as np
import glob
from PIL import Image
# read the train images
train_dir = 'ifd-train/'
num_classes = 61
X_train = []
y_train = []
for i in range(1,num_classes + 1):
filenames = train_dir + str(i) + '-*.jpg'
for filename in glob.glob(filenames):
y_train.append(i-1)
image = Image.open(filename)
X_train.append(np.array(image))
X_train = np.array(X_train)
y_train = np.array(y_train)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# read the test images
test_dir = 'ifd-test/'
X_test = []
y_test = []
for i in range(1,num_classes + 1):
filenames = test_dir + str(i) + '-*.jpg'
for filename in glob.glob(filenames):
y_test.append(i-1)
image = Image.open(filename)
X_test.append(np.array(image))
X_test = np.array(X_test)
y_test = np.array(y_test)
17
18
19
20
21
22
23
24
25
26
27
28
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Chuẩn hóa dữ liệu
# create random rows
r = np.arange(0,len(y_train))
np.random.shuffle(r)
X_train = X_train[r,:]
y_train = y_train[r]
# get the image parameters
num_train_samples = X_train.shape[0]
num_test_samples = X_test.shape[0]
height = X_train.shape[1]
width = X_train.shape[2]
# normalize the data samples
X_train = X_train.reshape(num_train_samples, height*width)
X_train = X_train.astype('float32') / 255
X_test = X_test.reshape(num_test_samples, height*width)
X_test = X_test.astype('float32') / 255
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Tìm tham số C
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score
X_train_accuracy = []
X_test_accuracy = []
for c in [0.0001,0.001,0.01,0.1,1,10,100,1000,10000]:
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
X_train_accuracy.append(accuracy_score(y_train, y_train_pred))
X_test_accuracy.append(accuracy_score(y_test, y_test_pred))
# plot for determining c
c = [0.0001,0.001,0.01,0.1,1,10,100,1000,10000]
import matplotlib.pyplot as plt
plt.subplots(figsize=(10, 5))
plt.semilogx(c, X_train_accuracy,'-gD', color = 'blue', label="Training Accuracy")
plt.semilogx(c, X_test_accuracy,'-gD', color='red' , label="Testing Accuracy")
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Vẽ tỷ lệ nhận dạng theo tham số C
Tỷ lệ nhận dạng tập huấn luyện: 100%
Tỷ lệ nhận dạng tập kiểm tra: 90.16%
plt.grid(True)
plt.xlabel("Cost Parameter C",fontsize=14)
plt.ylabel("Accuracy",fontsize=14)
plt.legend()
plt.title('Accuracy versus the Cost Parameter C (log-scale)')
plt.show()
# run for c = 0.1
c = 0.1
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
# predict
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
# accuracy
X_train_accuracy = accuracy_score(y_train, y_train_pred)
X_test_accuracy = accuracy_score(y_test, y_test_pred)
#
print(X_train_accuracy)
print(X_test_accuracy)
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
Bài tập
Nhận dạng chữ viết tay
Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Cho siêu phẳng
, 󰉵
󰇛
󰇜
, khi  vector vuông góc
với siêu phẳng
.
Giải sử 2 điểm
nằm trên siêu phẳng, khi
đó ta :
Tức
󰇛

󰇜 , điều này nghĩa rằng
vector vuông góc với siêu phẳng.
2
1
Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Khoảng cách từ điểm 󰇛
󰇜
đến một siêu phẳng
, 󰉵
󰇛
󰇜
Vector vuông góc với siêu phẳng
.
Vector cùng hướng với vector , do đó hướng
của vector là:

.
Chiều dài của vecor , do đó vector được
xác định là:
Xét điểm hiệu bởi hình vuông, ta :
󰆒
.
 điểm trên siêu phằng, nên
 .


Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Thay vào
 , ta :

, tức

Nếu xét điểm hiệu bởi hình tròn, ta :
󰆒
. Tương tự ta :

Khoảng cách từ đến
:




Phụ lục B – Phương pháp Lagrangian Multiplers
Xem tài liệu